package test230609;

import java.util.Scanner;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/9 19:25
 * 5. 回文子串
 * https://leetcode.cn/problems/longest-palindromic-substring/
 */
public class Solution02 {

    // 中心扩散法
    public  static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        int n = s.length();
        char[] sCharArray = s.toCharArray();
        String res = "";  // 记录最长回文子串
        int maxLen = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= 1; j++) {
                int left = i;
                int right = i + j;  // 当 j == 1 时, 中心点有两个字符
                while (left >= 0 && right < n && sCharArray[left] == sCharArray[right]){
                    int len = right - left + 1;
                    if (len > maxLen) {
                        maxLen = len;
                        res = s.substring(left, left + len);
                    }
                    --left;
                    ++right;
                }
            }
        }
        return res;
    }

    // 动态规划
    public static String longestPalindrome2(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        int n = s.length();
        boolean[][] dp = new boolean[n][n];  // dp[i][j] 表示 s[i, j] 是否为一个回文串
        int maxLen = 0;
        int begin = 0;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                int len = j - i + 1;
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

        // 用于测试
    public static void main(String[] args) {
        String input = new Scanner(System.in).next();
        String longestPalindrome = longestPalindrome(input);
        System.out.println(longestPalindrome);
    }
}
